package com.yulongtian.weekCompetition.month202212.week1;

import java.util.*;

/**
 * 可
 *
 * @author yulongTian
 * @create 2022-12-04 11:06
 */
public class Test03 {
    public static void main(String[] args) {
        int n = 4;
        int[][] roads = {{1, 2, 9}, {2, 3, 6}, {2, 4, 5}, {1, 4, 7}};

        System.out.println(minScore(n, roads));
    }

    public static int minScore(int n, int[][] roads) {

        //标志 某点是否被遍历过 1 为有
        int[] flag = new int[n + 1];


        //节点  后续节点集合
        HashMap<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < roads.length; i++) {
            int x = roads[i][0];
            int y = roads[i][1];

            if (map.containsKey(x)) {
                List<Integer> integerList = map.get(x);
                integerList.add(y);
                map.put(x, integerList);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(y);
                map.put(x, temp);
            }
            if (map.containsKey(y)) {
                List<Integer> integerList = map.get(y);
                integerList.add(x);
                map.put(y, integerList);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(x);
                map.put(y, temp);
            }
        }


        //队列
        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(1);
        flag[1] = 1;

        while (!queue.isEmpty()) {

            //节点
            Integer poll = queue.poll();

            //后续节点
            List<Integer> integers = map.get(poll);
            for (Integer integer : integers) {
                //没有访问过
                if (flag[integer] != 1) {
                    queue.add(integer);
                    flag[integer] = 1;
                }
            }


        }

        int res = Integer.MAX_VALUE;

        for (int i = 0; i < roads.length; i++) {
            int x = roads[i][0];
            int y = roads[i][1];
            int dis = roads[i][2];

            if (flag[x] == 1 || flag[y] == 1) {
                res = Math.min(res, dis);
            }


        }

//        System.out.println(Arrays.toString(flag));

        return res;
    }

}
